package lanqiao._02算法训练.page01;

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 问题描述
 * 　　有N根木棍，需要将其粘贴成M个长木棍，使得最长的和最短的的差距最小。
 * 输入格式
 * 　　第一行两个整数N,M。
 * 　　一行N个整数，表示木棍的长度。
 * 输出格式
 * 　　一行一个整数，表示最小的差距
 * 样例输入
 * 3 2
 * 10 20 40
 * 样例输出
 * 10
 * 数据规模和约定
 * 　　N, M<=7
 * 思路：
 * dfs 枚举
 * 将一个木棍沾到其他木棍上
 * 操作次数： n - m
 * vis 数组 当 i 位的木棍使用了 vis[i] = true
 * 枚举所有可能记录最小差
 * @since 2022 - 10 - 30 - 20:47
 */
public class _10沾木棍 {
}
class Main10{
    static int n, m;
    static int[] nums;
    //vis 数组 当 i 位的木棍使用了 vis[i] = true
    static boolean[] vis;
    static int res;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        nums = new int[n];
        vis = new boolean[n];
        res = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            nums[i] = sc.nextInt();
        }
        //将一个木棍沾到另一个木棍上，需操作 n - m 次
        dfs(n - m);
        System.out.println(res);
    }
    static void dfs(int cnt){
        if(cnt == 0){   //得到了m个木棍
            //计算最长木棍和最短木棍的差
            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            for(int i = 0; i < n ; i++){
                //得到的m个木棍vis[i] = false
                if(!vis[i]){
                    min = Math.min(min, nums[i]);
                    max = Math.max(max, nums[i]);
                }
            }
            //记录最小差
            res = Math.min(res, max - min);
            return;
        }
        //选一个木棍
        for(int i = 0; i < n; i++){
            if(!vis[i]){    //没用过
                vis[i] = true;
                //选择一个其他的木棍粘过去
                for(int j = 0; j < n; j++){
                    //不是当前的木棍 没用过
                    if(j != i && !vis[j]){
                        nums[j] += nums[i];
                        dfs(cnt - 1);
                        //回溯
                        nums[j] -= nums[i];
                    }
                }
                //回溯
                vis[i] = false;
            }
        }
    }
}
//错误的思路：每次选两个最短的 合成一个新的
class Main10_1{
    static int n, m;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        PriorityQueue<Integer> minheap = new PriorityQueue<>();
        for(int i = 0; i < n; i++){
            minheap.offer(sc.nextInt());
        }
        while(minheap.size() > m){
            int n1 = minheap.poll();
            int n2 = minheap.poll();
            minheap.offer(n1 + n2);
        }
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int num : minheap){
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        System.out.println(max - min);
    }

}
